import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/14 10:29
 * @description 做不出来，焯！
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {6, 3, 8, 1, 3, 1, 2, 2};
        solution.minimumIncompatibility(nums, 4);
    }

    int ans = Integer.MAX_VALUE;
    int size = 0;
    boolean isSame = true;
    public int minimumIncompatibility(int[] nums, int k) {
        int n = nums.length;
        int[] cnt = new int[17];
        for (int i : nums) {
            cnt[i]++;
        }
        for (int i = 1; i <= 16; i++) {
            // n能够被k整除
            if (cnt[i] > n / k) {
                // 无法被分成 k个子集，使得每个子集内元素都不同
                return -1;
            }
        }
        // 由于数据量小，应该可以搜索回溯 + 剪枝
        Arrays.sort(nums);
        int[] distribute = new int[n];
        boolean[] vis = new boolean[n];
        // 每个子集的大小
        size = n / k;
        backtrack(nums, distribute, 0, k, vis);
        return ans;
    }

    private void backtrack(int[] nums, int[] distribute, int i, int k,  boolean[] vis) {
        if (i == nums.length) {
            int sum = 0;
            for (int j = 0; j < nums.length; j++) {
                if (j % size == size - 1) {
                    sum += distribute[j] - distribute[j - size + 1];
                }
            }
            ans = Math.min(ans, sum);
            return;
        }
        if (i != 0 && i % size == 0) {
            isSame = true;
        }
        for (int j = 0; j < nums.length; j++) {
            if (!vis[j]) {
                if (isSame && (j > 0 && nums[j] == nums[j - 1])) {
                    // 同一个子集里避免相同
                    continue;
                }
                distribute[i] = nums[j];
                vis[j] = true;
                backtrack(nums, distribute, i + 1, k,  vis);
                vis[j] = false;
                distribute[i] = 0;
            }
        }
    }
}

